#include <stack>

using namespace std;

// 最小栈
// 测试链接 : https://leetcode.cn/problems/min-stack/
// push 时，min 栈和 data 栈都 push 数据
class MinStack 
{
private:
    stack<int> data;
    stack<int> min;

public:
    MinStack() 
    {}
    
    void push(int val) 
    {
        data.push(val);
        if(min.empty() || val <= min.top())
        {
            min.push(val);
        }
        else // !min.empty() && val > min.top()
        {
            min.push(min.top());
        }
    }
    
    void pop() 
    {
        min.pop();
        data.pop();
    }
    
    int top() 
    {
        return data.top();
    }
    
    int getMin() 
    {
        return min.top();
    }
};

// push 时，data 栈会 push 数据，而 min 栈只有
// 当 val 小于 min.top() 时或 min 栈为空时，才会
// 将 val push 到 min 栈中
class MinStack 
{
private:
    stack<int> data;
    stack<int> min;

public:
    MinStack() 
    {}
    
    void push(int val) 
    {
        data.push(val);
        if(min.empty() || val <= min.top())
        {
            min.push(val);
        }
    }
    
    void pop() 
    {
        // 如果 data 栈的 top 等于 min 栈的 top，则
        // min 栈中 pop 掉一个最小值
        if(data.top() == min.top())
        {
            min.pop();
        }
        data.pop();
    }
    
    int top() 
    {
        return data.top();
    }
    
    int getMin() 
    {
        return min.top();
    }
};

// leetcode的数据在测试时，同时在栈里的数据不超过这个值
// 这是几次提交实验出来的，哈哈
// 如果leetcode补测试数据了，超过这个量导致出错，就调大
class MinStack 
{
private:
    static const int MAXN = 8001;
    int* data;
    int* min;
    int sz;

public:
    MinStack() 
    {
        data = new int[MAXN];
        min = new int[MAXN];
        sz = 0;
    }
    
    void push(int val) 
    {
        data[sz] = val;
        if(sz == 0 || val <= min[sz - 1])
            min[sz] = val;
        else
            min[sz] = min[sz - 1];
        ++sz;
    }
    
    void pop() 
    {
        --sz;
    }
    
    int top() 
    {
        return data[sz - 1];
    }
    
    int getMin() 
    {
        return min[sz - 1];
    }
};